from typing import List


class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n = len(seats), len(seats[0])

        # 定义状态表格
        dp = [[0] * (1 << n) for _ in range(m + 1)]

        # 将seats的每一行转化为二进制数：被占用的座位表示为1，未占用的座位表示为1
        nums = []
        for i in range(m):
            v = 0
            for j in range(n):
                if seats[i][j] == "#":
                    v += (1 << j)
            nums.append(v)

        # 状态转移
        for i in range(m - 1, -1, -1):  # 从后向前遍历
            for j in range(1 << n):
                # 当前行没有连续坐人：not j & j << 1 and not j & j >> 1
                # 当前行坐人没有坐在坏桌椅上：j & nums[i]
                if not j & j << 1 and not j & j >> 1 and not j & nums[i]:
                    for k in range(1 << n):  # 遍历上一行的所有状态
                        # 这一行没有坐在上一行斜前方的人：not j & k << 1 and not j & k >> 1
                        if not j & k << 1 and not j & k >> 1:
                            dp[i][j] = max(dp[i][j], dp[i + 1][k] + bin(j).count("1"))

        return max(dp[0])


if __name__ == "__main__":
    # 4
    print(Solution().maxStudents(seats=[["#", ".", "#", "#", ".", "#"],
                                        [".", "#", "#", "#", "#", "."],
                                        ["#", ".", "#", "#", ".", "#"]]))

    # 3
    print(Solution().maxStudents(seats=[[".", "#"],
                                        ["#", "#"],
                                        ["#", "."],
                                        ["#", "#"],
                                        [".", "#"]]))

    # 10
    print(Solution().maxStudents(seats=[["#", ".", ".", ".", "#"],
                                        [".", "#", ".", "#", "."],
                                        [".", ".", "#", ".", "."],
                                        [".", "#", ".", "#", "."],
                                        ["#", ".", ".", ".", "#"]]))

    # 测试用例53/55 : 9
    print(Solution().maxStudents(seats=[["#", "#", "#", ".", "#"],
                                        [".", ".", "#", ".", "."],
                                        ["#", ".", "#", ".", "#"],
                                        [".", ".", ".", ".", "."],
                                        [".", ".", ".", "#", "."]]))
